package dp.base;

import java.util.Arrays;

public class Solution_279 {

    int[][]memo;

    public int numSquares(int n) {
        int m= (int) (Math.sqrt(n)+1);
        memo=new int[m][n+1];
        for (int i = 0; i < m; i++) {
            Arrays.fill(memo[i],-1);
        }
        return dfs(m-1,n);
    }

    private int dfs(int i, int j) {
        if(i==0){
            if(j==0)
                return 0;
            return Integer.MAX_VALUE/2;
        }
        if(memo[i][j]!=-1)
            return memo[i][j];
        if(j<i*i)
            return memo[i][j]=dfs(i-1,j);
        return memo[i][j]=Math.min(dfs(i-1,j),dfs(i,j-i*i)+1);
    }

    public static void main(String[] args) {
        Solution_279 solution279 = new Solution_279();
        System.out.println(solution279.numSquares(13));
    }
}
